package com.draby.starfantasymaze.methods.maze;

import com.draby.starfantasymaze.dto.map.Block;
import com.draby.starfantasymaze.dto.map.Map;
import com.draby.starfantasymaze.enums.StatusCode;
import com.draby.starfantasymaze.methods.IGenerateMaze;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 使用凿墙算法自动生成迷宫
 * 凿墙规则如下：
 * 1. 只有当隔壁格子没去过的时，才可凿墙
 * 2. 该格子周围无墙可凿时，随机传送到一个之前去过的格子
 * 3. 每一个格子都要访问一次
 */
public class DigWallAlgorithm implements IGenerateMaze {
    /**
     * 存放所有访问过的格子，当访问格子周围均无可访问格子时移除该格子
     */
    private List<Block> visitedBlocks = new ArrayList<>();

    /**
     * 本次访问的格子周围可访问的格子
     */
    private List<Block> hasBlocks = new ArrayList<>();

    /**
     * 生成一个迷宫
     * @param map 已生成好的地图
     * @return true: 迷宫生成成功，否则返回 false
     */
    @Override
    public boolean generateMaze(Map map) {
        // 选择一个格子作为起点，行列索引应在迷宫范围内，且该格可访问
        Random r = new Random();
        Block[][] maze = map.getMaze();
        int xIdx = 0;
        int yIdx = 0;
        // 判断是否可以访问，不能访问则循环寻找能访问的格子
        boolean canVisit = false;
        while (!canVisit) {
            xIdx = r.nextInt(maze.length);
            yIdx = r.nextInt(maze[xIdx].length);
            // 寻找到可以访问的格子
            if (StatusCode.UNVISITED.equals(maze[xIdx][yIdx].getStatusCode())) {
                canVisit = true;
            }
        }
        // 使用凿墙算法生成迷宫
        digWall(map.getMaze(), map.getMaze()[xIdx][yIdx]);
        return true;
    }

    /**
     * 凿墙算法实现步骤
     * 1. 将该格子置为已访问并判断所有格子是否已全访问
     *    a. 已经全访问完毕，则迷宫创建完成
     *    b. 将该格子添加到已访问列表(若不存在于列表中)，并执行第 2 步
     * 2. 判断该格子周围是否有未访问格子
     *    a. 若没有，则将该格子置为无可访问，并移出列表，再在列表中随机选择一个格子
     *    b. 若有，则在周围格子随机选择一个格子，并凿通这堵墙
     * 3. 确定访问格子后回到第 1 步继续执行
     *
     * @param maze 迷宫
     * @param block 迷宫中的某一个格子
     */
    private void digWall(Block[][] maze, Block block) {
        // 1
        System.out.print("(" + block.getRowIdx() + ", " + block.getColIdx() + ") -> ");
        block.setStatusCode(StatusCode.VISITED);
        if (!allVisited(maze)) {
            // 1 -> b
            if (!visitedBlocks.contains(block)) {
                visitedBlocks.add(block);
            }
            Random r = new Random();
            int length;
            int next;
            Block block1;
            if (hasNoVisited(maze, block.getRowIdx(), block.getColIdx())) {
                // 2 -> b
                length = hasBlocks.size();
                next = r.nextInt(length);
                block1 = hasBlocks.get(next);
                // 向上凿
                if (block1.getRowIdx() < block.getRowIdx()) {
                    block.setCanUp(true);
                    block1.setCanDown(true);
                }
                // 向下凿
                else if (block1.getRowIdx() > block.getRowIdx()) {
                    block.setCanDown(true);
                    block1.setCanUp(true);
                }
                // 向左凿
                else if (block1.getColIdx() < block.getColIdx()) {
                    block.setCanLeft(true);
                    block1.setCanRight(true);
                }
                // 向右凿
                else if (block1.getColIdx() > block.getColIdx()) {
                    block.setCanRight(true);
                    block1.setCanLeft(true);
                }
            } else {
                // 2 -> a
                block.setStatusCode(StatusCode.AROUND_VISITED);
                visitedBlocks.remove(block);
                length = visitedBlocks.size();
                next = r.nextInt(length);
                block1 = visitedBlocks.get(next);
            }
            // 3
            digWall(maze, block1);
        }
        // 1 -> a
    }

    /**
     * 检查是否将所有格子访问完毕
     *
     * @param maze 迷宫
     * @return true: 所有格子访问完，否则返回 false
     */
    private boolean allVisited(Block[][] maze) {
        for (Block[] blocks : maze) {
            for (Block block : blocks) {
                if (StatusCode.UNVISITED.equals(block.getStatusCode())) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 检查周围是否有未访问格子
     *
     * @param maze 迷宫
     * @param xIdx 该格子的行索引
     * @param yIdx 该格子的列索引
     * @return true: 周围有未访问格子，否则返回 false
     */
    private boolean hasNoVisited(Block[][] maze, int xIdx, int yIdx) {
        // 检查是否索引是否越界
        if (xIdx < 0 || yIdx < 0) {
            return false;
        }
        int height = maze.length;
        if (xIdx > height) {
            return false;
        }
        int width = maze[xIdx].length;
        if (yIdx > width) {
            return false;
        }
        // 清除列表中的项
        hasBlocks.clear();
        boolean has = false;
        // 检查四个方位的格子是否有没有被访问过的
        // 判断上方格子
        if (xIdx - 1 >= 0) {
            if (StatusCode.UNVISITED.equals(maze[xIdx - 1][yIdx].getStatusCode())) {
                hasBlocks.add(maze[xIdx - 1][yIdx]);
                has = true;
            }
        }
        // 判断下方格子
        if (xIdx + 1 < height) {
            if (StatusCode.UNVISITED.equals(maze[xIdx + 1][yIdx].getStatusCode())) {
                hasBlocks.add(maze[xIdx + 1][yIdx]);
                has = true;
            }
        }
        // 判断左方格子
        if (yIdx - 1 >= 0) {
            if (StatusCode.UNVISITED.equals(maze[xIdx][yIdx - 1].getStatusCode())) {
                hasBlocks.add(maze[xIdx][yIdx - 1]);
                has = true;
            }
        }
        // 判断右方格子
        if (yIdx + 1 < width) {
            if (StatusCode.UNVISITED.equals(maze[xIdx][yIdx + 1].getStatusCode())) {
                hasBlocks.add(maze[xIdx][yIdx + 1]);
                has = true;
            }
        }
        return has;
    }
}
